{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flatten a Multilevel Doubly Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #linked-list #doubly-linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #链表 #双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flatten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扁平化多级双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 <strong>子指针</strong> 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 <strong>多层数据结构</strong> 。</p>\n",
    "\n",
    "<p>给定链表的头节点&nbsp;<font color=\"#c7254e\"><font face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size:12.6px\"><span style=\"background-color:#f9f2f4\">head</span></span></font></font>&nbsp;，将链表 <strong>扁平化</strong> ，以便所有节点都出现在单层双链表中。让 <code>curr</code> 是一个带有子列表的节点。子列表中的节点应该出现在<strong>扁平化列表</strong>中的&nbsp;<code>curr</code> <strong>之后</strong> 和&nbsp;<code>curr.next</code>&nbsp;<strong>之前</strong> 。</p>\n",
    "\n",
    "<p>返回 <em>扁平列表的 <code>head</code>&nbsp;。列表中的节点必须将其 <strong>所有</strong> 子指针设置为&nbsp;<code>null</code>&nbsp;。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/11/09/flatten11.jpg\" style=\"height:339px; width:700px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]\n",
    "<strong>输出：</strong>[1,2,3,7,8,11,12,9,10,4,5,6]\n",
    "<strong>解释：</strong>输入的多级列表如上图所示。\n",
    "扁平化后的链表如下图：\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/09/flatten12.jpg\" style=\"height:69px; width:1000px\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/11/09/flatten2.1jpg\" style=\"height:200px; width:200px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,null,3]\n",
    "<strong>输出：</strong>[1,3,2]\n",
    "<strong>解释：</strong>输入的多级列表如上图所示。\n",
    "扁平化后的链表如下图：\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/24/list.jpg\" style=\"height:87px; width:300px\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "<strong>说明：</strong>输入中可能存在空列表。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数目不超过 <code>1000</code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>如何表示测试用例中的多级链表？</strong></p>\n",
    "\n",
    "<p>以 <strong>示例 1</strong> 为例：</p>\n",
    "\n",
    "<pre>\n",
    " 1---2---3---4---5---6--NULL\n",
    "         |\n",
    "         7---8---9---10--NULL\n",
    "             |\n",
    "             11--12--NULL</pre>\n",
    "\n",
    "<p>序列化其中的每一级之后：</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null]\n",
    "[7,8,9,10,null]\n",
    "[11,12,null]\n",
    "</pre>\n",
    "\n",
    "<p>为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null]\n",
    "[null,null,7,8,9,10,null]\n",
    "[null,11,12,null]\n",
    "</pre>\n",
    "\n",
    "<p>合并所有序列化结果，并去除末尾的 null 。</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]\n",
    "</pre>\n",
    "\n",
    "<ul>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flatten-a-multilevel-doubly-linked-list](https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flatten-a-multilevel-doubly-linked-list](https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]', '[1,2,null,3]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: TreeNode):\n",
    "        \n",
    "        # Array containing all the nodes in the sorted order\n",
    "        self.nodes_sorted = []\n",
    "        \n",
    "        # Pointer to the next smallest element in the BST\n",
    "        self.index = -1\n",
    "        \n",
    "        # Call to flatten the input binary search tree\n",
    "        self._inorder(root)\n",
    "        \n",
    "    def _inorder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self._inorder(root.left)\n",
    "        self.nodes_sorted.append(root.val)\n",
    "        self._inorder(root.right)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        \"\"\"\n",
    "        @return the next smallest number\n",
    "        \"\"\"\n",
    "        self.index += 1\n",
    "        return self.nodes_sorted[self.index]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        \"\"\"\n",
    "        @return whether we have a next smallest number\n",
    "        \"\"\"\n",
    "        return self.index + 1 < len(self.nodes_sorted)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Tuple\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def myFlatten(self, head: 'Node') -> Tuple['Node']:\n",
    "        if head is None:\n",
    "            return (None, None)\n",
    "\n",
    "        p: 'Node' = head.prev\n",
    "        q: 'Nonde' = head\n",
    "        \n",
    "        while q is not None:\n",
    "            if q.child is not None:\n",
    "                dh, dt = self.myFlatten(q.child)\n",
    "                if q.next is not None:\n",
    "                    q.next.prev = dt\n",
    "                dt.next = q.next\n",
    "                dh.prev = q\n",
    "                q.next = dh\n",
    "                q.child = None\n",
    "                q = dt\n",
    "\n",
    "            p, q = q, q.next\n",
    "\n",
    "        return (head, p)\n",
    "\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        return self.myFlatten(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        walker = head\n",
    "        stack = []\n",
    "        while walker or stack:\n",
    "            if walker.child != None:\n",
    "                tmp = walker.next\n",
    "                if tmp:\n",
    "                    stack.append(tmp)\n",
    "                \n",
    "                child = walker.child\n",
    "                walker.next = child\n",
    "                child.prev = walker\n",
    "                walker.child = None\n",
    "            else:\n",
    "                if walker.next is None and stack:\n",
    "                    tmp = stack.pop()\n",
    "                    walker.next = tmp\n",
    "                    tmp.prev = walker\n",
    "                    #walker.next.prev = walker\n",
    "            walker = walker.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        list_res = []\n",
    "        def preOrder(root):\n",
    "            if not root:return None\n",
    "\n",
    "            list_res.append(root.val)\n",
    "            if root.child:\n",
    "                preOrder(root.child)\n",
    "            if root.next:\n",
    "                preOrder(root.next)\n",
    "        preOrder(head)\n",
    "        start = Node(0, None, None, None)\n",
    "        res = start\n",
    "        for each in list_res:\n",
    "            # print(each)\n",
    "            start.next = Node(each, start, None, None)\n",
    "            start = start.next\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        p = res = Node(None, None, None, None)\n",
    "        visited = head and [head]\n",
    "        while visited:\n",
    "            vertex = visited.pop()\n",
    "            if vertex.next:\n",
    "                visited.append(vertex.next)\n",
    "            if vertex.child:\n",
    "                visited.append(vertex.child)\n",
    "            p.next = vertex\n",
    "            p, p.prev, p.child = p.next, p, None\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head == None: return head\n",
    "        p, tail, stack = head, head, []\n",
    "        while p:\n",
    "            tail = p\n",
    "            if p.child:\n",
    "                if p.next: stack.append(p.next)\n",
    "                p.next = p.child\n",
    "                p.child.prev = p\n",
    "                p.child = None     \n",
    "            p = p.next\n",
    "            \n",
    "            if p: continue # p不为空执行上面的逻辑\n",
    "            if len(stack) > 0:\n",
    "                p = stack.pop()\n",
    "                tail.next = p\n",
    "                p.prev = tail\n",
    "                \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = [head]\n",
    "        pre = None\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "                node.child = None\n",
    "            if pre:\n",
    "                node.prev = pre\n",
    "                pre.next = node\n",
    "            pre = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        node = head\n",
    "        while node:\n",
    "            if node.child:\n",
    "                if node.next: # 如果存在 next 部分\n",
    "                    stack.append(node.next) # 就保存\n",
    "                node.child.prev = node # 让 node.child 变成 node.next\n",
    "                node.next = node.child # 同上\n",
    "                node.child = None # 置空 node.child\n",
    "            elif (not node.next) and stack: # 如果走到底没有next了，就把之前保存的 next 拿出来\n",
    "                last_next = stack.pop() # stack里最后一个就是最新的 next\n",
    "                node.next = last_next # 让它，变成当前 node 的 next\n",
    "                last_next.prev = node\n",
    "                \n",
    "            node = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        stack =[]\n",
    "        pa = head\n",
    "        while pa:\n",
    "            if pa.child:\n",
    "                if pa.next:\n",
    "                    stack.append(pa.next)\n",
    "                pa.child.prev = pa\n",
    "                pa.next = pa.child\n",
    "                pa.child = None\n",
    "                pa = pa.next\n",
    "            else:\n",
    "                if pa.next:\n",
    "                    pa.child = None\n",
    "                    pa.next.prev = pa\n",
    "                    pa = pa.next\n",
    "                if not pa.next:\n",
    "                    pa.child = None\n",
    "                    if stack:\n",
    "                        pa.next = stack.pop()\n",
    "                        pa.next.prev = pa\n",
    "                        pa = pa.next\n",
    "                    else:\n",
    "                        pa = pa.next\n",
    "                        break\n",
    "        return head\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        h = Node(0,None,None,None)\n",
    "        h1 = h\n",
    "        stack.append(head)\n",
    "        \n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            \n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "            h.next = node\n",
    "            node.prev,node.next,node.child = h,None,None\n",
    "            h = h.next\n",
    "        if h1.next:\n",
    "            h1.next.prev = None\n",
    "        return h1.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        res=head\n",
    "        tmp=[]\n",
    "        while head:\n",
    "            if head.child!=None:\n",
    "                if head.next!=None:\n",
    "                    tmp.append(head.next)\n",
    "                head.next=head.child\n",
    "                head.child=None\n",
    "                head.next.prev=head\n",
    "            if head.next!=None:\n",
    "                head=head.next\n",
    "            else:\n",
    "                if tmp!=[]:\n",
    "                    tmp1=tmp.pop()\n",
    "                    head.next=tmp1\n",
    "                    tmp1.prev=head\n",
    "                    head=head.next\n",
    "                else:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None \n",
    "        curr = head\n",
    "        while curr:\n",
    "            if curr.child:\n",
    "                n = curr.next \n",
    "                curr.next, curr.child.prev = curr.child, curr \n",
    "                curr.child = None \n",
    "                curr.next = self.flatten(curr.next)\n",
    "                while curr.next:\n",
    "                    curr = curr.next \n",
    "                if n:\n",
    "                    curr.next, n.prev = n, curr \n",
    "            else:\n",
    "                curr = curr.next \n",
    "        return head \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head \n",
    "        \n",
    "        pseudoHead = Node(None, None, head, None)\n",
    "        self.flatten_dfs(pseudoHead, head)\n",
    "\n",
    "        pseudoHead.next.prev = None\n",
    "        return pseudoHead.next\n",
    "\n",
    "    def flatten_dfs(self, pre, curr):\n",
    "        if not curr:\n",
    "            return pre \n",
    "        \n",
    "        curr.prev = pre \n",
    "        pre.next = curr \n",
    "\n",
    "        tempNext = curr.next\n",
    "        tail = self.flatten_dfs(curr, curr.child)  # flatten sub chain \n",
    "        curr.child = None\n",
    "        return self.flatten_dfs(tail, tempNext)   \n",
    "        # connect biconnection between the flattened sub chain and the root's next node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        headpre = Node(None,None,head,None)\n",
    "        self.dfs(headpre,head)\n",
    "        headpre.next.prev = None\n",
    "        return headpre.next\n",
    "    def dfs(self,pre,cur):\n",
    "        if not cur:\n",
    "            return pre\n",
    "        pre.next = cur\n",
    "        cur.prev = pre\n",
    "        tmp = cur.next\n",
    "        tail = self.dfs(cur,cur.child)\n",
    "        cur.child = None\n",
    "        return self.dfs(tail,tmp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if head.child:\n",
    "                end = dfs(head.child)\n",
    "                if head.next: # 如果有后续节点\n",
    "                    end.next = head.next \n",
    "                    end.next.prev = end \n",
    "                head.next = head.child\n",
    "                head.child.prev = head \n",
    "                head.child = None # 删除子节点\n",
    "            if head.next:\n",
    "                return dfs(head.next)\n",
    "            else:\n",
    "                return head \n",
    "        if not head: \n",
    "            return head \n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:  #这里需要判断一下，避免第一级的尾结点存在child节点的情况\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        s = deque()\n",
    "        cur = head\n",
    "        prev = None\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                if cur.next:\n",
    "                    next = cur.next\n",
    "                    next.prev = None\n",
    "                    s.append(next)\n",
    "                cur.next = cur.child\n",
    "                cur.next.prev = cur\n",
    "                cur.child = None\n",
    "            prev = cur\n",
    "            cur = cur.next\n",
    "        cur = prev\n",
    "        while s:\n",
    "            cur.next = s.pop()\n",
    "            cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        \n",
    "        find_child = head\n",
    "\n",
    "        while find_child != None:\n",
    "            if find_child.child:\n",
    "                \n",
    "                ptr = find_child\n",
    "\n",
    "                temp = ptr.next\n",
    "                child = ptr.child\n",
    "                child.prev = ptr\n",
    "                \n",
    "                while child.next:\n",
    "                    child = child.next\n",
    "\n",
    "                ptr.next = ptr.child\n",
    "\n",
    "                ptr.child = None\n",
    "                child.next = temp\n",
    "                if temp:\n",
    "                    temp.prev = child\n",
    "            \n",
    "            find_child = find_child.next\n",
    "\n",
    "            head.prev = None\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                start = end = cur.child\n",
    "                while end.next:\n",
    "                    end = end.next\n",
    "                end.next = cur.next\n",
    "                if cur.next:\n",
    "                    cur.next.prev = end\n",
    "                cur.child = None\n",
    "                cur.next = start\n",
    "                start.prev = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self,head:\"Node\")->\"Node\":\n",
    "        def dfs(node:Node)->Node:\n",
    "            cur=node\n",
    "            last=None\n",
    "            while cur:\n",
    "                next=cur.next\n",
    "                if cur.child:\n",
    "                    childLast=dfs(cur.child)\n",
    "                    next=cur.next\n",
    "                    cur.next=cur.child\n",
    "                    cur.child.prev=cur\n",
    "                    cur.child=None\n",
    "                    if next:\n",
    "                        next.prev=childLast\n",
    "                        childLast.next=next\n",
    "                    last=childLast\n",
    "                else:\n",
    "                    last=cur\n",
    "                cur=next\n",
    "            return last\n",
    "        if head==None:return None\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(head):\n",
    "            pre = None\n",
    "            while head:\n",
    "                if not head.child:\n",
    "                    pre = head\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    nxt = head.next\n",
    "                    childLast = dfs(head.child)\n",
    "                    head.next = head.child\n",
    "                    head.child.prev = head\n",
    "                    head.child = None\n",
    "                    childLast.next = nxt\n",
    "                    if nxt:\n",
    "                        nxt.prev = childLast\n",
    "                    pre = childLast\n",
    "                    head = nxt\n",
    "            return pre\n",
    "\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def link_child(node_father:'Node', node_child:'Node'):\n",
    "            if not node_child:\n",
    "                return node_father\n",
    "            node_father.next = node_child\n",
    "            node_child.prev = node_father\n",
    "\n",
    "            next_child = node_child.next\n",
    "            tail = link_child(node_child, node_child.child)\n",
    "\n",
    "            node_child.child = None\n",
    "\n",
    "            return link_child(tail, next_child)\n",
    "            \n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        tmp = Node(-1, None, None, None)\n",
    "        tmp.next = head\n",
    "        \n",
    "        link_child(tmp, head)\n",
    "        tmp.next.prev = None\n",
    "        \n",
    "        return tmp.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        s = head\n",
    "        while s:\n",
    "            if s.child:\n",
    "                nex = s.next\n",
    "                cur = s.child\n",
    "\n",
    "                s.next = cur\n",
    "                s.child = None\n",
    "                cur.prev = s\n",
    "                while cur.next:\n",
    "                    cur = cur.next\n",
    "                if nex:\n",
    "                    nex .prev = cur\n",
    "                cur.next = nex\n",
    "            s = s.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        visitor = head\n",
    "        while visitor != None:\n",
    "            if visitor.child == None:\n",
    "                visitor = visitor.next\n",
    "                continue\n",
    "            childvisitor = visitor.child\n",
    "            while childvisitor.next != None:\n",
    "                childvisitor = childvisitor.next\n",
    "            childvisitor.next = visitor.next\n",
    "            if visitor.next != None:\n",
    "                visitor.next.prev = childvisitor\n",
    "            visitor.next = visitor.child\n",
    "            visitor.child.prev = visitor\n",
    "            visitor.child = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        self.dfs(head)\n",
    "        return head\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        while node.next and not node.child:\n",
    "            node = node.next\n",
    "        \n",
    "        tail = None\n",
    "        if node.child:\n",
    "            tail = self.dfs(node.child)\n",
    "\n",
    "            temp = node.next\n",
    "            node.next = node.child\n",
    "            node.child.prev = node\n",
    "            node.child = None\n",
    "            tail.next = temp\n",
    "            if temp:\n",
    "                temp.prev = tail\n",
    "            return self.dfs(tail)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    \n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None, None\n",
    "            \n",
    "            head = tail = node\n",
    "            child = node.child\n",
    "            nex = node.next\n",
    "            node.next = None\n",
    "            node.child = None\n",
    "            \n",
    "            son_head, son_tail = dfs(child)\n",
    "            if son_head:\n",
    "                head.next = son_head\n",
    "                head.next.prev = head\n",
    "                tail = son_tail\n",
    "\n",
    "            post_head, post_tail = dfs(nex)\n",
    "            if post_head:\n",
    "                tail.next = post_head\n",
    "                tail.next.prev = tail\n",
    "                tail = post_tail\n",
    "            return head, tail\n",
    "\n",
    "        return dfs(head)[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
